package cn.edu.besti.cs1823.G2326;

public class Sreaching {
    public static Comparable LinearSearch(Comparable[] data,Comparable target)
    {
        Comparable result=null;
        int index=0;

        while(result==null&&index<data.length)
        {
            if(data[index].compareTo(target)==0)
                result=data[index];
            index++;
        }
        return result;
    }
    //二分查找
    public static Comparable binarySearch(Comparable[] data,Comparable target)
    {
        Comparable result=null;
        int first=0,last=data.length,mid;

        while(result==null&&first<=last)
        {
            mid=(first+last)/2;
            if(data[mid].compareTo(target)==0)
                result=data[mid];
            else
            if(data[mid].compareTo(target)>0)
                last=mid-1;
            else
                first=mid+1;
        }
        return result;
    }
    //顺序查找
    public static<T>
    boolean linearSearch(T[] data,int min,int max,T target)
    {
        int index=min;
        boolean found=false;

        while(!found&&index<=max)
        {
            found=data[index].equals(target);
            index++;
        }
        return found;
    }
    // 插值查找
    public static int InsertionSearch(int[] a, int value, int low, int high) {
        int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
        if (a[mid] == value) {
            return mid;
        }
        if (a[mid] > value) {
            return InsertionSearch(a, value, low, mid - 1);
        } else {
            return InsertionSearch(a, value, mid + 1, high);
        }
    }

    // 斐波那契查找
    // 使用递归建立斐波那契数列
    public static int Fibonacci(int n) {
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

    public static int FibonacciSearch(int[] data,int n,int key) {
        int low = 1;
        int high = n;
        int mid;


        int k = 0;
        while (n > Fibonacci(k) - 1) {
            k++;
        }

        int[] temp = new int[Fibonacci(k)];
        System.arraycopy(data, 0, temp, 0, data.length);

        for (int i = n + 1; i <= Fibonacci(k) - 1; i++) {
            temp[i] = temp[n];
        }

        while (low <= high) {
            mid = low + Fibonacci(k - 1) - 1;
            if (temp[mid] > key) {
                high = mid - 1;
                k = k - 1;
            }
            else if (temp[mid] < key)
            {
                low = mid + 1;
                k = k - 2;
            } else {
                if (mid <= n) {
                    return mid;
                }
                else {
                    return n;
                }
            }
        }
        return 0;
    }
}
